package leetcode

import kotlinetc.println

//https://leetcode.com/problems/climbing-stairs/

fun main(args: Array<String>) {
    climbStairs(3).println()
}

//DP 虽然简单，但是一道非常直观的动态规划题目
fun climbStairs(n: Int): Int {

    if (n < 3) return n

//    val dp = IntArray(n + 1) { 0 }
//    dp[1] = 1
//    dp[2] = 2
//
//    for (i in 3..n) {
//
//        dp[i] = dp[i - 1] + dp[i - 2]
//    }
//
//    return dp[n]


    val result = 0

    var a = 1
    var b = 2

    for (i in 3..n) {
        val c = a
        a = b
        b += c

    }
    return b
}